package org.example.struct.array2;

import java.util.*;

/**
 * @author liyishan
 * @date 2023/10/12 09:18
 * @apiNote
 */

public class Test00621LeastInterval {

    public static void main(String[] args) {
        char[] tasks = new char[]{'A','A','A','B','B','B'};
        int count = test(tasks,2);
        System.out.println(count);
    }
    public static int test(char[] tasks, int n) {
        Map<Character,Integer> freq =  new HashMap<>();
        for(char c : tasks){
            freq.put(c,freq.getOrDefault(c,0)+1);
        }
        int m = freq.size();
        List<Integer> nextValid = new ArrayList<>();
        List<Integer> rest = new ArrayList<>();
        for(Map.Entry<Character,Integer> entry : freq.entrySet()){
            int value = entry.getValue();
            nextValid.add(1);
            rest.add(value);
        }
        int time = 0;
        for(int i = 0; i < tasks.length; i++){
            ++time;
            int minNext = Integer.MAX_VALUE;
            for(int j = 0; j < m; j++){
                if(rest.get(j) != 0){
                    minNext = Math.min(minNext,nextValid.get(j));
                }
            }
            time = Math.max(time,minNext);
            int best = -1;
            for(int j = 0; j < m; j++){
                if(rest.get(j) != 0 && nextValid.get(j) <= time){
                    if(best == -1 || rest.get(j) >rest.get(best)){
                        best = j;
                    }
                }
            }
            nextValid.set(best,time+n+1);
            rest.set(best,rest.get(best)-1);
        }
        return time;
    }



    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<Character, Integer>();
        // 最多的执行次数
        int maxExec = 0;
        for (char ch : tasks) {
            int exec = freq.getOrDefault(ch, 0) + 1;
            freq.put(ch, exec);
            maxExec = Math.max(maxExec, exec);
        }
        // 具有最多执行次数的任务数量
        int maxCount = 0;
        Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
        for (Map.Entry<Character, Integer> entry : entrySet) {
            int value = entry.getValue();
            if (value == maxExec) {
                ++maxCount;
            }
        }
        return Math.max((maxExec - 1) * (n + 1) + maxCount, tasks.length);
    }
}
